/*
* Authors: Karymov Anton
*          Skorodumov Kirill
* This file contains implementation of branching algorythm.
* June-August,	2011
*/


#include "branching_algorythm.h"
#include "types.h"

using namespace boost;
using namespace std;

branching_algorythm::branching_algorythm(graph_t & g_) {
  g = g_;
  covered_map = get(edge_covered, g);
  included_map = get(vertex_included, g);
  name_map = get(vertex_name, g);
  covered_edges_count = 0;
  cover_size = 0;
  optimization_level = 0;
  processed_vertices.clear();
  processed_vertices.insert(processed_vertices.begin(),num_vertices(g),false);
}

unsigned int branching_algorythm::get_cover_size() const {
  return cover_size;
}

//this only a wrapper. all real work is done by internal _solve
bool branching_algorythm::solve(const int k) {
  graph_traits<graph_t>::vertex_iterator i, iend;
  if (k >= (int)num_vertices(g)) {
    for (tie(i, iend) = vertices(g); i != iend; ++i) {
      include_vertex(*i);
    }
    return true;
  }

  int k1 = k;
  if (optimization_level >= 1) {
    optimization_degree_one(k1);
  }

  bool result = internal_solve(k1);

  if (!result) {
    for (tie(i, iend) = vertices(g); i != iend; ++i) {
      exclude_vertex(*i);
    }
    covered_edges_count = 0;
    cover_size = 0;
  }
  else if ((int)cover_size < k)
  {
    for (tie(i, iend) = vertices(g); i != iend; ++i) {
      if ((int)cover_size == k) break;
      include_vertex(*i);
    }
  }

  return result;
}


bool branching_algorythm::internal_solve(int k)  {
  vertex_t v = 0;
  bool uncovered_vertex_exists = false;

  if (graph_already_covered() && (k >= 0)) {
    return true;
  }

  if (k <= 0)
  {
    return false;
  }

  graph_traits<graph_t>::vertex_iterator i, iend;
  for (tie(i, iend) = vertices(g); i != iend; ++i) {
    if (!get_include(*i) && !processed_vertices[*i]) {
      v = *i;
      uncovered_vertex_exists = true;
      break;
    }
  }
  if(!uncovered_vertex_exists || (graph_already_covered() && k>=0)) return true;

  if (branch(v, k))
  {
    return true;
  } else {
    return false;
  }
}

void branching_algorythm::set_cover(edge_t e, bool value) {
  if (value && !covered_map[e]) {
    covered_edges_count++;
  }
  else if (!value && covered_map[e]) {
    covered_edges_count--;
  }
  covered_map[e] = value;
}

bool branching_algorythm::get_cover(edge_t e) const {
  return covered_map[e];
}

void branching_algorythm::set_include(vertex_t v, bool value) {
  if (value && !included_map[v]) {
    cover_size++;
  }
  else if (!value && included_map[v]) {
    cover_size--;
  }
  included_map[v] = value;
}

bool branching_algorythm::get_include(vertex_t v) const {
  return included_map[v];
}

int branching_algorythm::uncovered_neighbours(vertex_t v) {
  graph_traits<graph_t>::adjacency_iterator i, iend;
  int result = 0;

  for(tie(i, iend) = adjacent_vertices(v, g); i != iend; ++i) {
    if (!get_cover(edge(v, *i, g).first)) result++;
  }

  return result;
}

bool branching_algorythm::graph_already_covered() const {
  return num_edges(g) == covered_edges_count;
}



//include vertex in cover
void branching_algorythm::include_vertex(vertex_t v) {
  graph_traits<graph_t>::adjacency_iterator i, iend;

  if (get_include(v)) {
    return;
  }

  for(tie(i, iend) = adjacent_vertices(v, g); i != iend; ++i) {
      set_cover(edge(v, *i, g).first, true);
  }

  set_include(v, true);
}


//exclude previously included vertex
void branching_algorythm::exclude_vertex(vertex_t v) {
  graph_traits<graph_t>::adjacency_iterator i, iend;

  if (!get_include(v)) {
    return;
  }

  for(tie(i, iend) = adjacent_vertices(v, g); i != iend; ++i) {
      set_cover(edge(v, *i, g).first, false);
  }

  set_include(v, false);
}

bool branching_algorythm::branch(vertex_t v, int k) {

  processed_vertices[v] = true;

  if (graph_already_covered() && (k >= 0)) {
    return true;
  }

  if (k <= 0)
  {
    return false;
  }

  int res;
  //trying to include given vertex
  include_vertex(v);

  res = internal_solve(k - 1);

  if (res) {
    return true;
  }

  exclude_vertex(v);

  graph_traits<graph_t>::adjacency_iterator i, iend;

  list<vertex_t> need_exclude;
  //trying to include all neighbours of given vertex
  for(tie(i, iend) = adjacent_vertices(v, g); i != iend; ++i) {
    if (!get_include(*i)) {
      include_vertex(*i);
      need_exclude.push_back(*i);
    }
  }

  res = internal_solve(k - need_exclude.size());

  if (res) {
    return true;
  }

  for(list<vertex_t>::iterator i = need_exclude.begin(); i != need_exclude.end(); ++i) {
    exclude_vertex(*i);
  }

  return false;
}

void branching_algorythm::optimization_degree_one(int & k) {
  graph_traits <graph_t>::vertex_iterator i,iend;
  graph_traits <graph_t>::adjacency_iterator j, jend;
  bool found = false;

  for (tie(i,iend) = vertices(g); i != iend; ++i) {
    if (k <= 0) return;
    if ((uncovered_neighbours(*i) == 1))
    { 
      found = true;
      k--;
      for (tie(j, jend) = adjacent_vertices(*i, g); j != jend; ++j){		
        include_vertex(*j);
      }
    }	
  }

  if(found){
    optimization_degree_one(k);
  }
}

int branching_algorythm :: number_of_vertices() const {
  int size = num_vertices(g);
  return size;
}

void branching_algorythm::set_optimization_level(unsigned int level) {
  optimization_level = level;
}

boost::property_map<graph_t, boost::vertex_name_t>::type branching_algorythm::get_name_map() {
  return name_map;
}

void branching_algorythm::fill_name_map() {
  graph_traits <graph_t>::vertex_iterator i,iend;

  for (tie(i,iend) = vertices(g); i != iend; ++i) {
    if (get_include(*i)) name_map[*i] = "cover";
  }
}